# This file is part of Sonedyan.
#
# Sonedyan is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public
# License as published by the Free Software Foundation;
# either version 3 of the License, or (at your option) any
# later version.
#
# Sonedyan is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied
# warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
# PURPOSE.  See the GNU General Public License for more
# details.
#
# You should have received a copy of the GNU General Public.
# If not, see <http://www.gnu.org/licenses/>.
#
# Copyright (C) 2009-2012 Jimmy Dubuisson <jimmy.dubuisson@gmail.com>

library(igraph)

g <- read.graph(file = "eckmann-dataset.xml", format = "graphml")

# set nodes 'name' attribute
V(g)$name <- V(g)$id

printGlobalStats <- function(g, name)
{
  print(paste("Printing stats for '", name, "'"))
  print(paste("# vertices: ", length(V(g))))
  print(paste("# edges: ", length(E(g))))
  print(paste("Graph density: ", graph.density(g, loops=FALSE)))
}

printAllStats <- function(g, name)
{
  print(paste("Printing stats for '", name, "'"))
  print(paste("# vertices: ", length(V(g))))
  print(paste("# edges: ", length(E(g))))
  print(paste("Graph density: ", graph.density(g, loops=FALSE)))

  # get graph clusters
  wccs = clusters(g, mode="weak")
  sccs = clusters(g, mode="strong")

  print(paste("# wccs: ", wccs$no))
  print(paste("# sccs: ", sccs$no))

  print(paste("max wcc: ", max(wccs$csize)))
  print(paste("max scc: ", max(sccs$csize)))
}

# recursive deletion of source nodes
sourcesDeletion <- function(adj)
{
  while(TRUE)
  {
    size <- ncol(adj)
    currentSize <- size
    print(paste("matrix size: ", size))
    
    i <- 1

    while (i <= currentSize)
    {
	v <- adj[,i]
    
	if (sum(v) == 0)
	{
	  adj <- adj[-i,-i]
	  currentSize <- currentSize - 1
	}
	else
	{
	  #print(paste("   keeping column: ", i))
	}

	i <- i + 1
    }

    if (size == currentSize) break
  }

  return(adj)
}

# recursive deletion of source nodes
sourcesDeletion2 <- function(g)
{
  length <- length(V(g))
  g <- delete.vertices(g, which(degree(g, mode="in") == 0) - 1)
  if (length(V(g)) < length)
    return(sourcesDeletion2(g))
  else
    return(g)
}

# Eckmann shave: remove sources and sinks recursively
shave <- function(g)
{
  length <- length(V(g))
  g <- delete.vertices(g, which(degree(g, mode="in") == 0) - 1)
  g <- delete.vertices(g, which(degree(g, mode="out") == 0) - 1)
  if (length(V(g)) < length)
    return(shave(g))
  else
    return(g)
}

# get main SCC vertex IDs
getMainSccVertexIds <- function(g)
{
  sccs = clusters(g2, mode="strong")
  maxSccSize <- max(sccs$csize)
  # igraph is 0 based but R is 1 based...
  maxSccId = which(sccs$csize == maxSccSize)[1] - 1
  return(which(sccs$membership == maxSccId) - 1)
}

printVertexNames <- function(g, vertexIds)
{
  for (i in c(1:length(vertexIds)))
  {
    print(V(g)[vertexIds[i] + 1]$name)
  }
}

printAllStats(g, "Original graph")

# 'name' vertex attribute must be present in the graph
#a <- get.adjacency(g, names = TRUE, sparse = TRUE)
#adj <- sourcesDeletion(a)
# col names are added by default as attribute 'name'
#g2 <- graph.adjacency(adj, mode="directed")

g2 <- sourcesDeletion2(g)
g2b <- shave(g)

printAllStats(g2, "Sources deleted graph")
printAllStats(g2b, "Shaved graph")

mainSccVertexIds = getMainSccVertexIds(g2)

#printVertexNames(g2, mainSccVertexIds)

# set nodes 'label' attribute
V(g2)$label <- V(g2)$name

g3 <- subgraph(g2, mainSccVertexIds)

write.graph(g3, file= "core-graphml.xml", format = "graphml")
write.graph(g3, file= "core-gml.gml", format = "gml")

printGlobalStats(g3, "Main SCC graph")

print(V(g3)$name)
